// leetcode 21 合并两个有序链表
// 输入：l1 = [1,2,4], l2 = [1,3,4]
// 输出：[1,1,2,3,4,4]
var mergeTwoLists = function(l1, l2) {
    if(l1 == null){
        return l2;
    }else if(l2 == null){
        return l1;
    }else if(l1.val < l2.val){
        l1.next = mergeTwoLists(l1.next,l2);//小的值先合并
        return l1;
    }else if(l1.val>=l2.val){
        l2.next = mergeTwoLists(l1,l2.next);
        return l2;
    }
};
// leetcode 141 判断一个单链表是否有环
var hasCycle = function(head) {
    let slow = head,fast = head;
    while(fast && fast.next){
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast){
            return true;
        }
    }  
    return false;
};

//leetcode206 反转链表
// 输入: 1->2->3->4->5->NULL
// 输出: 5->4->3->2->1->NULL
//迭代解法
var reverseList = function(head) {
    let pre = null,cur=head,nxt=head;
    while(cur != null){
        nxt = cur.next;
        cur.next = pre; //这一行注意
        pre = cur;
        cur = nxt;
    }
    return pre;
};
//递归
var reverseList = function(head) {
   if(!head || head.next == null) return head;
   let last = reverseList(head.next);
   head.next.next = head;
   head.next = null;
   return last;
};

//leetcode 876 求链表的中间结点
//[1,2,3,4,5] => 3
//[1,2,3,4,5,6] => 4
// https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484505&idx=1&sn=0e9517f7c4021df0e6146c6b2b0c4aba&chksm=9bd7fa51aca07347009c591c403b3228f41617806429e738165bd58d60220bf8f15f92ff8a2e&scene=21#wechat_redirect
var middleNode = function(head) {
   let slow = fast = head;
   while(fast && fast.next){
       slow = slow.next;
       fast = fast.next.next;
   }
   return slow;
};
//leetcode 19 删除链表倒数第n个结点
// 输入：head = [1,2,3,4,5], n = 2
// 输出：[1,2,3,5]
//注意：可以和 返回链表第K个节点的题目对比
var removeNthFromEnd = function(head, n) {
   let slow = fast = head;
   while(n--){
       fast = fast.next;
   }
   if(fast == null){
       return head.next;
   }
   while(fast && fast.next){
       slow = slow.next;
       fast = fast.next;
   }
   slow.next = slow.next.next;
   return head;
};
//leetcode 160  编写一个程序，找到两个单链表相交的起始节点
//listA = [4,1,8,4,5], listB = [5,0,1,8,4,5] 相交点为8
var getIntersectionNode = function(headA, headB) {
   let pa = headA,pb=headB;
   while(pa || pb){
       if(pa == pb){
           return pa;
       }
       pa = pa == null ? headB : pa.next;
       pb = pb == null ? headA : pb.next;
   }
   return null;
};

//leetcode 2 链表求和
// 输入：l1 = [2,4,3], l2 = [5,6,4]
// 输出：[7,0,8]
// 解释：342 + 465 = 807.
var addTwoNumbers = function(l1, l2) {
    let sum = new ListNode('0');
    let head = sum;
    let addOne = 0;
    while(l1 || l2){
       let val1 = l1 ? l1.val : 0;
       let val2 = l2 ? l2.val : 0;
       let r = val1+val2+addOne;
       addOne = r >=10 ? 1: 0;
       sum.next = new ListNode(r%10);
       sum = sum.next;
       if(l1) l1 = l1.next;
       if(l2) l2 = l2.next;
    }
    return head.next;
};
// 92. 反转链表2
//反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
var reverseBetween = function(head, left, right) {
    //递归方法
    let successor;
    const reverseN = (head,n)=>{
        if(n === 1){
            successor = head.next;
            return head;
        }
        let last = reverseN(head.next,n-1);
        head.next.next = head;
        head.next = successor;
        return last;
    }
    if(left === 1){
        return reverseN(head,right);
    }
    head.next = reverseBetween(head.next,left-1,right-1);
    return head;
};
//25. K 个一组翻转链表
var reverseKGroup = function(head, k) {
     const reverseNode = (a,b)=>{
         let pre = null,cur=nxt = a;
         while(cur!=b){
             nxt = cur.next;
             cur.next = pre;
             pre = cur;
             cur = nxt;
         }
         return pre;
     }
     if(head == null) return null;
     let a = b = head;
     for(let i=0;i<k;i++){
         if(b == null) return head;
         b = b.next;
     }
     let newHead = reverseNode(a,b);
     a.next = reverseKGroup(b,k);
     return newHead;

};
//234.回文链表
//请判断一个链表是否为回文链表。
var isPalindrome = function(head) {
    let fast = head,slow = head;
    while(fast && fast.next){
        fast = fast.next.next;
        slow = slow.next;
    }
    if(fast !== null){
        slow = slow.next;
    }
    const reverse = (head)=>{
        let pre = null,cur=nxt = head;
        while(cur){
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
    let left = head,right = reverse(slow);
    while(right){
        if(left.val !== right.val) return false;
        left = left.next;
        right = right.next;
    }
    return true;
};

//递归解法：
var left;
var isPalindrome = function(head) {
  left = head;
  return traverse(head);
};
var traverse = function(right){
   if(right == null) return true;
   let res = traverse(right.next);
   res = res && (right.val == left.val);
   left = left.next;
   return res;
}